/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import org.jheaps.AddressableHeap
import org.jheaps.annotations.LinearTime
import java.io.Serializable

/**
 * An array based binary addressable heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The implementation uses an array in order to store the elements and
 * automatically maintains the size of the array much like a
 * [java.util.Vector] does, providing amortized O(log(n)) time cost for
 * the `insert` and `deleteMin` operations. Operation
 * `findMin`, is a worst-case O(1) operation. Operations `delete`
 * and `decreaseKey` take worst-case O(log(n)) time. The bounds are
 * worst-case if the user initializes the heap with a capacity larger or equal
 * to the total number of elements that are going to be inserted into the heap.
 *
 *
 *
 * Constructing such a heap from an array of elements can be performed using the
 * method [.heapify] or
 * [.heapify] in linear time.
 *
 *
 *
 * Note that the ordering maintained by a binary heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `Heap` interface. (See `Comparable` or `Comparator` for a
 * precise definition of *consistent with equals*.) This is so because
 * the `Heap` interface is defined in terms of the `equals`
 * operation, but a binary heap performs all key comparisons using its
 * `compareTo` (or `compare`) method, so two keys that are deemed
 * equal by this method are, from the standpoint of the binary heap, equal. The
 * behavior of a heap *is* well-defined even if its ordering is
 * inconsistent with `equals`; it just fails to obey the general contract
 * of the `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
class BinaryArrayAddressableHeap<K, V>
/**
 * Constructs a new, empty heap, with a provided initial capacity ordered
 * according to the given comparator.
 *
 *
 *
 * All keys inserted into the heap must be *mutually comparable* by
 * the given comparator: `comparator.compare(k1,
 * k2)` must not throw a `ClassCastException` for any keys `k1`
 * and `k2` in the heap. If the user attempts to put a key into the
 * heap that violates this constraint, the `insert(Object key)` call
 * will throw a `ClassCastException`.
 *
 *
 *
 * The initial capacity of the heap is provided by the user and is adjusted
 * automatically based on the sequence of insertions and deletions. The
 * capacity will never become smaller than the initial requested capacity.
 *
 * @param comparator
 * the comparator that will be used to order this heap. If
 * `null`, the [natural ordering][Comparable] of
 * the keys will be used.
 * @param capacity
 * the initial heap capacity
 */
/**
 * Constructs a new, empty heap, using the natural ordering of its keys.
 *
 *
 *
 * All keys inserted into the heap must implement the [Comparable]
 * interface. Furthermore, all such keys must be *mutually
 * comparable*: `k1.compareTo(k2)` must not throw a
 * `ClassCastException` for any keys `k1` and `k2` in the
 * heap. If the user attempts to put a key into the heap that violates this
 * constraint (for example, the user attempts to put a string key into a
 * heap whose keys are integers), the `insert(Object key)` call will
 * throw a `ClassCastException`.
 *
 *
 *
 * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
 * adjusts automatically based on the sequence of insertions and deletions.
 */
/**
 * Constructs a new, empty heap, ordered according to the given comparator.
 *
 *
 *
 * All keys inserted into the heap must be *mutually comparable* by
 * the given comparator: `comparator.compare(k1,
 * k2)` must not throw a `ClassCastException` for any keys `k1`
 * and `k2` in the heap. If the user attempts to put a key into the
 * heap that violates this constraint, the `insert(Object key)` call
 * will throw a `ClassCastException`.
 *
 *
 *
 * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
 * adjusts automatically based on the sequence of insertions and deletions.
 *
 * @param comparator
 * the comparator that will be used to order this heap. If
 * `null`, the [natural ordering][Comparable] of
 * the keys will be used.
 */
@JvmOverloads constructor(comparator: Comparator<in K?>? = null, capacity: Int = DEFAULT_HEAP_CAPACITY) :
    AbstractArrayAddressableHeap<K, V>(comparator, capacity), Serializable {
    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param capacity
     * the initial heap capacity
     */
    constructor(capacity: Int) : this(null, capacity)

    /**
     * Get an iterator for all handles currently in the heap.
     *
     * This method is especially useful when building a heap using the heapify
     * method. Unspecified behavior will occur if the heap is modified while
     * using this iterator.
     *
     * @return an iterator which will return all handles of the heap
     */
    fun handlesIterator(): Iterator<ArrayHandle> {
        return object : MutableIterator<ArrayHandle> {
            private var pos: Int = 1

            override fun hasNext(): Boolean {
                return pos <= size
            }

            override fun next(): AbstractArrayAddressableHeap<K,V>.ArrayHandle {
                if (pos > size) {
                    throw NoSuchElementException()
                }
                return array[pos++]!!
            }

            override fun remove() {
                throw UnsupportedOperationException()
            }
        }
    }

    /**
     * Ensure that the array representation has the necessary capacity.
     *
     * @param capacity
     * the requested capacity
     */
    override fun ensureCapacity(capacity: Int) {
        checkCapacity(capacity)
        /*val newArray: Array<ArrayHandle?> = java.lang.reflect.Array.newInstance(
            ArrayHandle::class.java, capacity + 1
        ) as Array<ArrayHandle>*/
        val newArray = arrayOfNulls<ArrayHandle>(capacity + 1)
        System.arraycopy(array, 1, newArray, 1, size)
        array = newArray
    }

    override fun forceFixup(k: Int) {
        var k: Int = k
        val h = array[k]
        while (k > 1) {
            array[k] = array[k / 2]
            array[k]!!.index = k
            k /= 2
        }
        array[k] = h
        h!!.index = k
    }

    override fun fixup(k: Int) {
        var k: Int = k
        val h  = array[k]!!
        while (k > 1 && (array[k / 2]?.key as Comparable<K>) > h.key) {
            array[k] = array[k / 2]
            array[k]!!.index = k
            k /= 2
        }
        array[k] = h
        h.index = k
    }

    override fun fixupWithComparator(k: Int) {
        var k: Int = k
        val h = array[k]!!
        while (k > 1 && comparator?.compare(array[k / 2]!!.key, h.key)!! > 0) {
            array[k] = array[k / 2]
            array[k]!!.index = k
            k /= 2
        }
        array[k] = h
        h.index = k
    }

    override fun fixdown(k: Int) {
        var k: Int = k
        val h = array[k]!!
        while (2 * k <= size) {
            var j: Int = 2 * k
            if (j < size && (array[j]!!.key as Comparable<K>) > array[j + 1]!!.key) {
                j++
            }
            if ((h.key as Comparable<K>) <= array[j]!!.key) {
                break
            }
            array[k] = array[j]
            array[k]!!.index = k
            k = j
        }
        array[k] = h
        h.index = k
    }

    override fun fixdownWithComparator(k: Int) {
        var k: Int = k
        val h = array[k]!!
        while (2 * k <= size) {
            var j: Int = 2 * k
            if (j < size && comparator!!.compare(array[j]!!.key, array[j + 1]!!.key) > 0) {
                j++
            }
            if (comparator!!.compare(h.key, array[j]!!.key) <= 0) {
                break
            }
            array[k] = array[j]
            array[k]!!.index = k
            k = j
        }
        array[k] = h
        h.index = k
    }

    companion object {

        /**
         * Default initial capacity of the binary heap.
         */
        val DEFAULT_HEAP_CAPACITY: Int = 16

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param <V>
         * the type of values maintained by the heap
         * @param keys
         * an array of keys
         * @param values
         * an array of values
         * @return a binary heap
         * @throws IllegalArgumentException
         * in case the array is null
        </V></K> */
        @JvmStatic
        @LinearTime
        fun <K, V> heapify(keys: Array<K>?, values: Array<V>?): BinaryArrayAddressableHeap<K, V> {
            if (keys == null) {
                throw IllegalArgumentException("Key array cannot be null")
            }
            if (values != null && keys.size != values.size) {
                throw IllegalArgumentException("Values array must have the same length as the keys array")
            }
            if (keys.isEmpty()) {
                return BinaryArrayAddressableHeap()
            }

            val h: BinaryArrayAddressableHeap<K, V> = BinaryArrayAddressableHeap(keys.size)

            for (i in keys.indices) {
                val key: K = keys[i]
                val value: V? = if ((values == null)) null else values[i]
                val ah = h.ArrayHandle(key, value)
                ah.index = i + 1
                h.array[i + 1] = ah
            }
            h.size = keys.size

            for (i in keys.size / 2 downTo 1) {
                h.fixdown(i)
            }

            return h
        }

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param <V>
         * the type of values maintained by the heap
         * @param keys
         * an array of keys
         * @param values
         * an array of values
         * @param comparator
         * the comparator to use
         * @return a binary heap
         * @throws IllegalArgumentException
         * in case the array is null
        </V></K> */
        @LinearTime
        fun <K, V> heapify(
            keys: Array<K>?, values: Array<V>?,
            comparator: Comparator<in K?>?
        ): BinaryArrayAddressableHeap<K, V> {
            if (keys == null) {
                throw IllegalArgumentException("Keys array cannot be null")
            }
            if (values != null && keys.size != values.size) {
                throw IllegalArgumentException("Values array must have the same length as the keys array")
            }
            if (keys.isEmpty()) {
                return BinaryArrayAddressableHeap(comparator)
            }

            val h: BinaryArrayAddressableHeap<K, V> = BinaryArrayAddressableHeap(comparator, keys.size)

            for (i in keys.indices) {
                val key: K = keys.get(i)
                val value: V? = if ((values == null)) null else values.get(i)
                val ah = h.ArrayHandle(key, value)
                ah.index = i + 1
                h.array[i + 1] = ah
            }
            h.size = keys.size

            for (i in keys.size / 2 downTo 1) {
                h.fixdownWithComparator(i)
            }

            return h
        }
    }
}
